package leetcode.od;

import org.junit.Test;

import java.util.*;

/**
 * @author pppppp
 * @date 2022/3/11 17:10
 * 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
 * <p>
 * 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
 * <p>
 * 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
 * <p>
 * 注意：不允许旋转信封。
 * <p>
 * 示例 1：
 * 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
 * 输出：3
 * 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
 * <p>
 * 示例 2:
 * 输入：envelopes = [[1,1],[1,1],[1,1]]
 * 输出：1
 */
public class _354_俄罗斯套娃信封问题 {

    @Test
    public void T_() {
        int [][][] nums = {
                {{5, 4}, {6, 4}, {6, 7}, {2, 3}},
                {{30, 50}, {12, 2}, {3, 4}, {12, 15}},
                {{3, 5}, {6, 7}, {3, 6}, {7, 20}},
                {{1,1}, {1,1},{1,1}},
                {{1, 15}, {7, 18}, {7, 6}, {7, 100}, {2, 200}, {17, 30}, {17, 45}, {3, 5}, {7, 8}, {3, 6}, {3, 10}, {7, 20}, {17, 3}, {17, 45}},
                {{21, 33}, {27, 39}, {6, 29}, {45, 2}, {5, 16}, {14, 15}, {31, 31}, {28, 43}, {14, 13}, {44, 29}, {44, 47}, {26, 1}, {40, 18}, {33, 6}, {39, 40}, {39, 13}, {1, 33}, {31, 4}, {21, 40}, {50, 14}, {17, 44}, {21, 22}, {32, 41}, {18, 28}, {29, 50}, {9, 24}, {25, 26}, {32, 30}, {17, 32}, {21, 2}, {17, 39}},
                {{1,3},{3,5},{6,7},{6,8},{8,4},{9,5}},
                {{2,1},{4,1},{6,2},{8,3},{10,5},{12,8},{14,13},{16,21},{18,34},{20,55}}
        };

        int [] ans = {3,3,3,1,3,7,3,9};
        for (int i = 0; i < nums.length; i++) {
            System.out.println(maxEnvelopes4(nums[i]) == ans[i]);
            // System.out.println(maxEnvelopes3(nums[i]));
        }
    }

    /*4.优化最长递增子序列
     * 贪心 + 二分法*/
    public int maxEnvelopes4(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o2[1] - o1[1];
                }
                return o1[0] - o2[0];
            }
        });

        /*动态规划 求解 y序列的最长递增子序列*/
        int[] dp = new int[envelopes.length + 1];
        dp[1] = envelopes[0][1];
        int maxLen = 1;
        for (int i = 1; i < envelopes.length; i++) {
            if (envelopes[i][1] == dp[maxLen]) {
                continue;
            }
            if (envelopes[i][1] > dp[maxLen]) {
                dp[++maxLen] = envelopes[i][1];
            } else {
                /*在有序的dp数组中找到大于当前 y 的最小值*/
                int index = binarySearch(dp, maxLen, envelopes[i][1]);
                dp[index] = envelopes[i][1];
            }
        }
        return maxLen;
    }

    private int binarySearch(int[] dp, int maxLen, int target) {
        int l = 1, r = maxLen;
        while (l <= r) {
            int mid = l + ((r-l)>>1);
            if(dp[mid] < target){
                l = mid+1;
            }else {
                r = mid-1;
            }
        }
        return l;
    }


    /*3.官方题解  动态规划--排序 + 最长严格单调递增子序列*/
    public int maxEnvelopes3(int[][] envelopes) {
        int max = 1;
        /*1.按行进行递增排序，这样排序后相邻序列fn(x1,y1),fn+1(x2,y2),x1<=x2,当x相同时，就只能从该堆中只取出一个数字，
         * 将相同x值的序列 按照y降序排列，这样y的最长单调递增子序列就是题解*/
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o2[1] - o1[1];
                }
                return o1[0] - o2[0];
            }
        });

        /*动态规划 求解 y序列的最长递增子序列*/
        int[] dp = new int[envelopes.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < envelopes.length; i++) {
            for (int j = 0; j <= i - 1; j++) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }


    /*2.转化为从起点到终点的最长路径的动态规划问题  超出了空间限制  */
    public int maxEnvelopes2(int[][] envelopes) {
        HashSet<Integer> x = new HashSet<>();
        HashSet<Integer> y = new HashSet<>();
        for (int[] envelope : envelopes) {
            if (!x.contains(envelope[0])) {
                x.add(envelope[0]);
            }
            if (!y.contains(envelope[1])) {
                y.add(envelope[1]);
            }
        }
        List<Integer> xList = new ArrayList<>(x);
        List<Integer> yList = new ArrayList<>(y);
        Collections.sort(xList);
        Collections.sort(yList);
        HashMap<Integer, Integer> xmap = new HashMap<>();
        HashMap<Integer, Integer> ymap = new HashMap<>();
        for (int i = 0; i < xList.size(); i++) {
            xmap.put(xList.get(i), i);
        }

        for (int i = 0; i < yList.size(); i++) {
            ymap.put(yList.get(i), i);
        }

        int[][] n = new int[xList.size()][yList.size()];
        for (int[] envelope : envelopes) {
            n[xmap.get(envelope[0])][ymap.get(envelope[1])] = 1;
        }

        for (int i = 0; i < n.length; i++) {
            String s = "";
            for (int j = 0; j < n[i].length; j++) {
                s += n[i][j];
            }
            System.out.println(s);
        }
        /*从倒数第二行向上连接*/
        int[] res = n[n.length - 1];

        for (int i = n.length - 2; i >= 0; i--) {
            for (int j = 0; j < n[0].length; j++) {
                if (n[i][j] == 1) {
                    if (j == n[0].length - 1) {
                        res[j] = 1;
                        continue;
                    }
                    int max = res[j + 1];
                    for (int k = j + 2; k < n[0].length; k++) {
                        if (res[k] > max) {
                            max = res[k];
                        }
                    }
                    res[j] = max + 1;
                }
            }
        }
        Arrays.sort(res);
        return res[res.length - 1];
    }

    /*1.空间超出限制*/
    public int maxEnvelopes(int[][] envelopes) {

        if (envelopes.length == 0) {
            return 0;
        }
        /*去重*/
        HashSet<String> set = new HashSet<>();
        List<int[]> list = new ArrayList<>();
        for (int[] envelope : envelopes) {
            if (!set.contains(envelope[0] + "-" + envelope[1])) {
                set.add(envelope[0] + "-" + envelope[1]);
                list.add(new int[]{envelope[0], envelope[1]});
            }
        }
        List<List<int[]>> jm = new ArrayList<>();
        List<int[]> t = new ArrayList<>();
        t.add(list.get(0));
        jm.add(t);
        int res = 1;
        for (int i = 1; i < list.size(); i++) {
            res = solution(list.get(i)[0], list.get(i)[1], res, jm);
        }
        return res;
    }

    private int solution(int x, int y, int res, List<List<int[]>> jm) {
        int size = jm.size();
        for (int i = 0; i < size; i++) {
            List<int[]> list = jm.get(i);
            int lSize = list.size();

            /*直接放在末尾*/
            if (x > list.get(lSize - 1)[0] && y > list.get(lSize - 1)[1]) {
                list.add(new int[]{x, y});
                res = Math.max(res, list.size());
                continue;
            }
            boolean add = false;
            int pos = 0;
            for (int j = 0; j < lSize; j++) {
                if (x < list.get(j)[0] && y < list.get(j)[1]) {
                    if (j > 0 && !(x > list.get(j - 1)[0] && y > list.get(j - 1)[1])) {
                        List<int[]> addList = new ArrayList<>();
                        addList.add(new int[]{x, y});
                        for (int k = j; k < list.size(); k++) {
                            addList.add(list.get(k));
                        }
                        res = Math.max(res, addList.size());
                        jm.add(addList);
                        add = true;
                        break;
                    }
                    list.add(j, new int[]{x, y});
                    add = true;
                    res = Math.max(res, list.size());
                    break;
                } else if (x > list.get(j)[0] && y > list.get(j)[1]) {
                    pos++;
                }
            }

            if (!add) {
                List<int[]> addList = new ArrayList<>();
                for (int j = 0; j < pos; j++) {
                    addList.add(list.get(j));
                }
                addList.add(new int[]{x, y});
                res = Math.max(res, addList.size());
                jm.add(addList);
            }
        }
        return res;
    }
}
